package diStringMatch;

import java.util.LinkedList;

//public class Solution {
//    public int[] diStringMatch(String s) {
//        // 思路，先把所有'I'按照升序填入，填入较小值
//        // 然后再把所有的'D'按照降序填入，填入较大值
//        int[] perm = new int[s.length()+1];
//        for (int i = 0; i < perm.length; i++) {
//            perm[i] = -1;
//        }
//        LinkedList<Integer> list = new LinkedList<>();
//        for (int i = 0; i <= s.length()+1; i++) {
//            list.addLast(i);
//        }
//        for (int i = 0; i < s.length(); i++) {
//            char c = s.charAt(i);
//            if(c=='I'){
//                // perm[i]<perm[i+1];
//                perm[i] = list.pollFirst();
//            }
//        }
//        for (int i = 0; i < perm.length; i++) {
//            if(perm[i] == -1){
//                perm[i] = list.pollLast();
//            }
//        }
//        return perm;
//    }
//}
class Solution {
    public int[] diStringMatch(String s) {
//        int n = s.length(), lo = 0, hi = n;
//        int[] perm = new int[n + 1];
//        for (int i = 0; i < n; ++i) {
//            perm[i] = s.charAt(i) == 'I' ? lo++ : hi--;
//        }
//        perm[n] = lo; // 最后剩下一个数，此时 lo == hi
//        return perm;
        int n = s.length(),min = 0,max = n;
        int[] prem = new int[n+1];
        for (int i = 0; i < n; ++i) {
            prem[i] = s.charAt(i) == 'I'?min++:max--;
        }
        prem[n] = max;
        return prem;
    }
}

